本文同步分享於個人Blog → InformisTry-HankLee

前言

最後一個主題拉～～～歡慶昨天中秋節～～～

最後一個主題我們要講的是貪婪的演算法(Greedy Algorithm)，前言廢話不多說，所以就開始吧～～

Greedy Algorithm是什麼

Greedy Algorithm的做法跟Dynamic Programming有點類似，都是一步一步將解答建構出來，Dynamic Programming在進行的時候，會將所以小解答記錄下來，然後再利用這些小解答來推導出答案；然而，Greedy Algorithm與之不同的地方是：Greedy Algorithm再一步步將解答建構出來的過程中，總是選擇當前最佳解來記錄下來。如此一來，當整個流程進行完成後，留下來的結果就是想要的成果了。

問題：在一個網絡系統中，依序找出由近至遠的節點

在處理這種問題時，基本上會先將所有擁有的資料變成Graph的形式，紀錄著節點與節點之間的關聯與這個關聯的代價(Weight)，然後再從預計的起始節點開始一路往後推導，而今天要介紹的這個方法叫做Prim's Algorithm，基本上步驟如下：

1. 選擇任一節點並加入清單。
2. 從這個節點開始，將其所有『鄰居』及『代價』記錄下來。
3. 從記錄中選出代價最低的節點加入清單。
4. 反覆進行2~3步，直到所有節點都加入了清單。

從上範例GIF中可以看到，假設我們預計起始點為Ａ，先在結果清單中將節點Ａ加入後，再從節點Ａ去計算其所有鄰居的距離，然後發現節點Ｅ的數值是最小的，因此將節點Ｅ放入結果清單，再從節點Ｅ來計算距離，而節點Ｅ唯一尚未加入結果清單的鄰居就只有節點Ｂ了，而且此時從節點Ｅ到節點Ｂ的距離是5，比原本的7還小，因此這時候節點Ｂ的數值被從7換成了5，然後再從Distance的紀錄中選出最小數值的節點加入結果清單，依此類推，直到所有節點都加入到結果清單。

小結

Prim's Algorithm執行的過程中，若有數值較小的狀況，其數值會被替換，並在爾後變成判斷的依據。

預告

明天我們將會介紹另外一種解決同一個問題的演算法 - Kruskal's Algorithm。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin